package datastructure.book.tujiesuanfa.queueastack.solution._1_easy;

import org.junit.jupiter.api.Test;

import java.util.*;

public class Solution1 {
    /**
     * 输入：heights = [14,2,27,-5,28,13,39], limit = 3
     * 输出：[27,27,28,28,39]
     * 解释：
     *   滑动窗口的位置                最大值
     * ---------------               -----
     * [14 2 27] -5 28 13 39          27
     * 14 [2 27 -5] 28 13 39          27
     * 14 2 [27 -5 28] 13 39          28
     * 14 2 27 [-5 28 13] 39          28
     * 14 2 27 -5 [28 13 39]          39
     * 1 <= limit <= heights.length
     * -10000 <= heights[i] <= 10000
     */
    public int[] maxAltitude(int[] heights, int limit) {
        if (heights == null || heights.length == 0) {
            return new int[0];
        }
        int i = 0;
        int j = limit-1;
        int k = maxNumberIndex(heights,i,j);
        int[] result = new int[heights.length - limit + 1];
        for (int m = 0; m < result.length; m++) {
            result[m] = heights[k];
            i++;j++;
            if (j < heights.length) {
                if (i <= k && k <= j) {
                    if (heights[k] <= heights[j]) {
                        k = j;
                    }
                } else {
                    k = maxNumberIndex(heights,i,j);
                }
            }
        }
        return result;
    }

    private int maxNumberIndex(int[] heights, int i, int j) {
        int max = heights[i];
        int maxIndex = i;
        while (i < j) {
            i++;
            if (max < heights[i]) {
                max = heights[i];
                maxIndex=i;
            }
        }
        return maxIndex;
    }
}
